// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 * Creator: yanking
 * Create time: 2022-03-01 14:52
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.Greedy;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class MaxNumber {
    // 拼接最大数，使用单调栈
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int m = nums1.length, n = nums2.length;
        int[] maxSubsequence = new int[k];
        int start = Math.max(0, k - n), end = Math.min(k, m);  // 从最小符合数量开始，知道数量达到当前数组的最大值
        for (int i = start; i <= end; i++) {// 保留每次产生的结果并且保留最好的结果->使用自定义比较器
            int[] subsequence1 = maxSubsequence(nums1, i);// 单调栈的使用，记录顺序下从大到小的次序
            int[] subsequence2 = maxSubsequence(nums2, k - i);
            int[] curMaxSubsequence = merge(subsequence1, subsequence2);
            if (compare(curMaxSubsequence, 0, maxSubsequence, 0) > 0) {// 自定义比较组成数字大小
                System.arraycopy(curMaxSubsequence, 0, maxSubsequence, 0, k);
            }
        }
        return maxSubsequence;
    }

    public int[] maxSubsequence(int[] nums, int k) {
        int length = nums.length;
        int[] stack = new int[k];
        int top = -1;
        int remain = length - k;
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            while (top >= 0 && stack[top] < num && remain > 0) {
                top--;
                remain--;
            }
            if (top < k - 1) {
                stack[++top] = num;
            } else {
                remain--;
            }
        }
        return stack;
    }

    public int[] merge(int[] subsequence1, int[] subsequence2) { // 使用自定义比较器实现两个挑选出的两个数组中顺序最大值得混合
        int x = subsequence1.length, y = subsequence2.length;
        if (x == 0) {
            return subsequence2;
        }
        if (y == 0) {
            return subsequence1;
        }
        int mergeLength = x + y;
        int[] merged = new int[mergeLength];
        int index1 = 0, index2 = 0; // 指针记录两个数组当前位置数字信息
        for (int i = 0; i < mergeLength; i++) {
            if (compare(subsequence1, index1, subsequence2, index2) > 0) {
                merged[i] = subsequence1[index1++];
            } else {
                merged[i] = subsequence2[index2++];
            }
        }
        return merged;
    }

    public int compare(int[] subsequence1, int index1, int[] subsequence2, int index2) {
        int x = subsequence1.length, y = subsequence2.length;
        while (index1 < x && index2 < y) { // 比较连个数字数组中组成数字的大小
            int difference = subsequence1[index1] - subsequence2[index2];
            if (difference != 0) {
                return difference;
            }
            index1++;
            index2++;
        }
        return (x - index1) - (y - index2); // 如果两个字符串前面部分相等则字符串长度长的一方大
    }


    @Test
    public void shout00() {
        int[] nums1 = {3, 4, 6, 5};
        int[] nums2 = {9, 1, 2, 5, 8, 3};
//        int[] nums1 = {3, 4};
//        int[] nums2 = {9, 1, 6};
        int k = 5;
        Arrays.stream(maxNumber(nums1, nums2, k)).forEach(System.out::println);
    }

}


